package com.study.algorithm.basicalsort.imp;

import com.study.algorithm.basicalsort.BasicalSort;

import java.util.List;

import static com.study.algorithm.utils.ListUtil.DeepClone;

/**
 * 插入排序
 * <p>
 * 原理：拿第一个索引位置值，排序
 * 拿第二个索引位置值，以特定顺序插入到第二个索引位置之前的位置（上一步导致前边元素已经有序）
 * 拿第三个索引位置值，以特定顺序插入到第san个索引位置之前的位置（上一步导致前边元素已经有序）
 * 。。。。。。
 * 直到最后一个索引位置值插入到对应位置，排序完毕
 */

public class InsertSortImpl implements BasicalSort {

    @Override
    public List<Integer> basicalSort(List<Integer> originList) {
        int size = originList.size();
        List<Integer> destList = DeepClone(originList);
        if (size <= 1) {
            return destList;
        }
        for (int currIndex = 0; currIndex < size; currIndex++) {
            insertIntoOrderList(destList, currIndex);
        }
        return destList;
    }

    private void insertIntoOrderList(List<Integer> list, int currIndex) {
        if (currIndex == 0) {
            return;
        }
        int inserVal = list.get(currIndex);
        int endInsertIndex = currIndex - 1;//将当前值插入到前n-1个有序值中
        int insertIndex = findInsertIndex(list, endInsertIndex, inserVal);
        if (insertIndex == currIndex) {
            return;
        }
        rightMoveForOnePosition(list, insertIndex, endInsertIndex);
        list.set(insertIndex, inserVal);
    }

    private int findInsertIndex(List<Integer> list, int endIndex, int inserVal) {
        int insertIndex = endIndex + 1;//代表无需插入，改值即为最大值
        for (int currIndex = 0; currIndex <= endIndex; currIndex++) {
            int currVal = list.get(currIndex);
            if (inserVal < currVal) {
                insertIndex = currIndex;
                break;
            }

        }
        return insertIndex;
    }

    private void rightMoveForOnePosition(List<Integer> list, int startInsertIndex, int endInsertIndex) {
        int size = list.size();
        if (startInsertIndex > endInsertIndex || endInsertIndex + 2 > size) {
            throw new ArrayIndexOutOfBoundsException("数组越界");
        }
        int preVal = list.get(startInsertIndex);
        for (int currIndex = startInsertIndex + 1; currIndex <= endInsertIndex + 1; currIndex++) {
            int currVal = list.get(currIndex);
            list.set(currIndex, preVal);
            preVal = currVal;
        }
    }
}
